class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        i, j = 0, len(nums)-1
        while i < j:
            if target < nums[i]:
                return i
            if target > nums[j]:
                return j + 1
            m = int((i + j) / 2)
            if target > nums[m]:
                i = m + 1
            else:
                j = m - 1
        if target > nums[i]:
            return i + 1
        return i

s = Solution()
nums = [1,3,5,6]
target = 5
result = s.searchInsert(nums, target)
print(result)

nums = [1,3,5,6]
target = 2
result = s.searchInsert(nums, target)
print(result)

nums = [1,3,5,6]
target = 7
result = s.searchInsert(nums, target)
print(result)
